package com.example.demo.linkedlist;

/**
 * 1) 单链表反转
 * 2) 链表中环的检测
 * 3) 两个有序的链表合并
 * 4) 删除链表倒数第n个结点
 * 5) 求链表的中间结点
 * @auther lijiewei
 * @date 2021/8/18 10:31
 */
public class LinkedListAlgo {

    /**
     * 单链表反转
     * @param headNode 单链表头结点
     * @return
     * @author lijiewei
     * @date   2021/8/18 10:57
     */
    public static Node reverse(Node headNode) {
        //遍历旧链表
        Node cur = headNode;
        Node next = null;
        //反转形成的新链表（上次插入的结点）
        Node pre = null;
        while (null != cur) {
            next = cur.getNext();
            //翻转插入新链表
            cur.setNext(pre);
            pre = cur;
            //继续遍历
            cur = next;
        }
        return pre;
    }

    /**
     * 检查链表中是否有环
     * @param headNode 链表头结点
     * @return
     * @author lijiewei
     * @date   2021/8/18 11:00
     */
    public static boolean checkCircle(Node headNode) {
        if (null == headNode) {
            return false;
        }
        //快指针，每次走2个结点
        Node fast = headNode.getNext();
        //慢指针，每次走1个结点
        Node slow = headNode;
        while (null != fast && null != fast.getNext()) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     *  两个有序的链表合并
     * @param head1 链表1的头结点
     * @param head2 链表2的头结点
     * @return
     * @author lijiewei
     * @date   2021/8/18 11:30
     */
    public static Node mergeTwoLinkedList(Node head1, Node head2) {
        //利用哨兵结点简化难度，否则需要先比较出头结点，再循环比较后续结点
        Node soldier = new Node(0);
        //新链表的插入点
        Node cur = soldier;
        while (head1 != null && head1 != null) {
            if (head1.getData() < head2.getData()) {
                cur.setNext(head1);
                head1 = head1.getNext();
            } else {
                cur.setNext(head2);
                head2 = head2.getNext();
            }
            cur = cur.getNext();
        }
        if (null != head1) {
            cur.setNext(head1);
        }
        if (null != head2) {
            cur.setNext(head2);
        }
        //返回链表去掉哨兵结点
        return soldier.getNext();
    }

    /**
     * 删除链表倒数第n个结点
     * @param head 链表头结点
     * @param k 倒数第k位
     * @return
     * @author lijiewei
     * @date   2021/8/18 13:44
     */
    public static Node deleteLastKth(Node head, int k) {
        //快指针
        Node fast = head;
        int i = 1;
        while (fast != null && i<k) {
            fast = fast.getNext();
            i++;
        }
        //链表一共没有k个结点，直接返回
        if (null == fast) {
            return head;
        }

        //慢指针，比快指针慢k位
        Node slow = head;
        //要删除的前一个结点
        Node pre = null;
        while (null != fast.getNext()) {
            fast = fast.getNext();
            pre = slow;
            slow = slow.getNext();
        }
        if (null == pre) {
            //刚好k个结点
            head = head.getNext();
        } else {
            pre.setNext(pre.getNext().getNext());
        }
        return head;
    }

    /**
     * 求链表的中间结点
     * @param head 链表头结点
     * @return
     * @author lijiewei
     * @date   2021/8/18 14:00
     */
    public static Node findMiddleNode(Node head) {
        if (null == head) {
            return null;
        }
        //快指针，每次移动两个结点
        Node fast = head;
        //慢指针，每次移动一个结点
        Node slow = head;

        while (null != fast && null != fast.getNext()) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        }
        return slow;
    }

    /**
     * 打印所有结点
     * @param head 头结点
     * @return
     * @author lijiewei
     * @date   2021/8/19 14:15
     */
    public static void printAll(Node head) {
        Node curNode = head;
        while (curNode != null) {
            System.out.print(head.getData() + " ");
            curNode = curNode.getNext();
        }
        System.out.println();
    }
}
